# coding: utf-8

import igraph as ig
import numpy as np
import random
import copy
from crossing_heuristic import (
    greedy_switch_heuristic,
    gravity_heuristics,
    reverse_gravity_heuristic,
)


def create_graph(num_vertices, edges):
    graph = ig.Graph(directed=True)
    graph.add_vertices(num_vertices)
    graph.add_edges(edges)
    return graph


def update_node_positions(graph, ordering):
    for layer in ordering:
        for i, node in enumerate(layer):
            graph.vs[node]["pos"] = i
    return graph


def mark_node(graph, ordering):
    for layer in ordering:
        for j, node in enumerate(layer):

            graph.vs[node]["mark"] = j + 1
    return graph


def logistic_tent_map(x, r):
    if x < 0.5:
        return (r * x * (1 - x) + (4 - r) * x / 2) % 1
    else:
        return (r * x * (1 - x) + (4 - r) * (1 - x) / 2) % 1


def chaotic_shuffle(layer, seed, chaotic_map):
    np.random.seed(int(seed * 10000))  # 根据种子值进行转换设置种子
    r = 4  # 设定r值，用于混沌映射
    x = seed
    order = []
    for _ in range(len(layer)):
        x = chaotic_map(x, r)
        order.append(x)
    sorted_indices = np.argsort(order)
    return [layer[i] for i in sorted_indices]


def earn_populations(num_populations, ordering):
    populations = []
    # 生成的映射种群
    for i in range(num_populations):
        seed = np.random.rand()  # 生成一个随机种子
        chaotic_sorted_layers = [
            chaotic_shuffle(layer, seed, chaotic_map_function) for layer in ordering
        ]
        populations.append(chaotic_sorted_layers)
    return populations


def calculate_reverse_individual(ordering):
    """
    计算反向个体
    """
    reverse_individual = []
    for sublist in ordering:

        max_pos = max([graph.vs[i]["mark"] for i in sublist])
        min_pos = min([graph.vs[i]["mark"] for i in sublist])
        reverse_sublist = [max_pos + min_pos - graph.vs[i]["mark"] for i in sublist]
        reverse_order = []
        for mark in reverse_sublist:
            sublist_copy = sublist[:]
            for i, node_pos in enumerate(sublist_copy):
                if graph.vs[node_pos]["mark"] == mark:
                    reverse_order.append(sublist_copy.pop(i))
                    break
        reverse_individual.append(reverse_order)
    return reverse_individual


def earn_reverse_population(populations):
    reverse_individual_populations = []
    for i in populations:
        reverse_individual = calculate_reverse_individual(i)
        reverse_individual_populations.append(reverse_individual)
    return reverse_individual_populations


def gather_populations(populations, reverse_individual_populations):
    # # 将映射种群和反向种群结合
    new_populations = populations + reverse_individual_populations
    return new_populations


def count_layer_crossings(graph, ordering, layer: int) -> int:
    upper = ordering[layer - 1]
    count: int = 0
    for i in range(len(upper) - 1):
        for u in graph.neighbors(upper[i], mode="out"):
            j = graph.vs[u]["pos"]
            for s in range(i + 1, len(upper)):
                for v in graph.neighbors(upper[s], mode="out"):
                    t = graph.vs[v]["pos"]
                    if (s > i and t < j) or (s < i and t > j):

                        count += 1

    return count


# 总层交叉数
def count_crossings(graph, h) -> int:
    update_node_positions(graph, h)
    count: int = 0
    for i in range(1, len(h)):
        count += count_layer_crossings(graph, h, i)

    return count


def sorted_population(graph, new_populations):
    fitness_values = []
    for ordering in new_populations:
        fitness_values.append(count_crossings(graph, ordering))
    sorted_indices = np.argsort(fitness_values)
    sorted_population = [new_populations[i] for i in sorted_indices]
    return sorted_population


def medium_range_reverse_on_lists(lists):
    # 定义一个函数，用于对单个列表执行中等范围反转
    def medium_range_reverse(lst):
        if len(lst) < 2:
            return lst
        idx1, idx2 = sorted(random.sample(range(len(lst)), 2))
        lst[idx1 : idx2 + 1] = lst[idx1 : idx2 + 1][::-1]
        return lst

    # 对包含的每个列表应用中等范围反转
    for lst in lists:
        medium_range_reverse(lst)
    return lists


def finder_bird(finder_bird_num, sorte_population, time, T):
    w_start_bird = 0.8
    w_end_bird = 0.2
    weight_factor_bird = w_start_bird - (w_start_bird - w_end_bird) * (
        2 * time / T - (time / T) ** 2
    )
    medium_movement_num = round(weight_factor_bird * finder_bird_num)
    greed_exchange_num = finder_bird_num - medium_movement_num
    # 进行贪婪交换
    for bird in sorte_population[:greed_exchange_num]:
        update_node_positions(graph, bird)
        greedy_switch_heuristic(bird, graph)
    # 进行中等范围交换
    for i in range(greed_exchange_num, finder_bird_num):
        bird = sorte_population[i]
        copy_bird = copy.deepcopy(bird)
        new_bird = medium_range_reverse_on_lists(copy_bird)
        if count_crossings(graph, new_bird) < count_crossings(graph, bird):
            sorte_population[i] = new_bird
    return sorte_population


def refine_individual(xi, w, p):
    # 初始化新个体列表
    xnew = copy.deepcopy(xi)  # 初始时复制xi的值
    # 确定哪些位置需要用p替换
    replace_indices = [i for i, (x, y) in enumerate(zip(xi, w)) if x == y]
    # 用p的值替换
    for index in replace_indices:
        xnew[index] = p[index]
    # 检查重复并去除原有值，用p中的新值填补
    used_values = set()
    to_fill = []  # 记录需要填充的位置
    for i in range(len(xnew)):
        if xnew[i] not in used_values:
            used_values.add(xnew[i])
        else:
            xnew[i] = None  # 标记为需要填充
            to_fill.append(i)
    # 使用未被使用的p中的值填充
    available_p = [v for v in p if v not in used_values]
    fill_iter = iter(available_p)
    for index in to_fill:
        try:
            xnew[index] = next(fill_iter)
        except StopIteration:
            break  # 如果p中没有足够的值来填充，终止填充
    return xnew


def generate_new_individuals(xi, w):
    num_chromosomes = len(xi)  # 计算染色体的数量
    new1 = [[] for _ in xi]  # 为新个体 x_new1 初始化空染色体列表
    new2 = [[] for _ in w]  # 为新个体 x_new2 初始化空染色体列表

    for i in range(num_chromosomes):
        size = len(xi[i])  # 当前染色体的基因长度
        if size > 1:
            num_elements = random.randint(1, size - 1)  # 随机选择交换的基因数量
            indices = random.sample(
                range(size), num_elements
            )  # 随机选择交换的基因的索引
        else:
            # 对于只有一个基因的染色体，我们直接交换该基因
            indices = [0]

        # 创建 x_new1 的当前染色体
        x_new1_chromosome = [None] * size
        remaining_xi = xi[i][:]  # 拷贝当前染色体

        for index in indices:
            x_new1_chromosome[index] = w[i][index]
            if w[i][index] in remaining_xi:
                remaining_xi.remove(w[i][index])  # 从剩余列表中移除已插入的 w 的元素

        # 填充 x_new1 当前染色体中未定义的位置
        pos = 0
        for j in range(size):
            if x_new1_chromosome[j] is None:
                x_new1_chromosome[j] = remaining_xi[pos]
                pos += 1
        new1[i] = x_new1_chromosome

        # 创建 x_new2 的当前染色体
        x_new2_chromosome = [None] * size
        remaining_w = w[i][:]  # 拷贝当前染色体

        for index in indices:
            x_new2_chromosome[index] = xi[i][index]
            if xi[i][index] in remaining_w:
                remaining_w.remove(xi[i][index])  # 从剩余列表中移除已插入的 xi 的元素

        # 填充 x_new2 当前染色体中未定义的位置
        pos = 0
        for j in range(size):
            if x_new2_chromosome[j] is None:
                x_new2_chromosome[j] = remaining_w[pos]
                pos += 1
        new2[i] = x_new2_chromosome

    return new1, new2


def follow_bird(
    follow_bird_num, sorte_population, p_best_bird, worst_bird, all_num_bird
):
    only_num = int((all_num_bird - follow_bird_num) / 2)
    x = sorte_population[follow_bird_num : follow_bird_num + only_num]

    # 靠近最优
    oooo = 0
    for xi in x:
        change_xi = []
        for xi_list, w_list, p_list in zip(xi, worst_bird, p_best_bird):
            change_xi.append(refine_individual(xi_list, w_list, p_list))

        if count_crossings(graph, change_xi) < count_crossings(
            graph, sorte_population[follow_bird_num + oooo]
        ):
            sorte_population[follow_bird_num + oooo] = change_xi
        oooo = oooo + 1

    # 远离最差
    yyyy = 0
    y = sorte_population[follow_bird_num + only_num :]
    for yi in y:
        x_new1, x_new2 = generate_new_individuals(yi, worst_bird)
        if count_crossings(graph, x_new1) < count_crossings(
            graph, sorte_population[follow_bird_num + only_num + yyyy]
        ):
            sorte_population[follow_bird_num + only_num + yyyy] = x_new1
        if count_crossings(graph, x_new2) < count_crossings(
            graph, sorte_population[follow_bird_num + only_num + yyyy]
        ):
            sorte_population[follow_bird_num + only_num + yyyy] = x_new2
    yyyy = yyyy + 1
    return sorte_population


num_vertices = 483
edges = [
    (1, 188),
    (2, 3),
    (2, 189),
    (3, 83),
    (4, 61),
    (4, 68),
    (5, 6),
    (6, 84),
    (6, 422),
    (7, 171),
    (7, 198),
    (8, 170),
    (9, 472),
    (11, 9),
    (11, 12),
    (12, 8),
    (12, 13),
    (13, 14),
    (14, 15),
    (15, 16),
    (16, 202),
    (17, 451),
    (18, 19),
    (19, 20),
    (19, 338),
    (20, 21),
    (20, 334),
    (21, 22),
    (21, 325),
    (22, 23),
    (22, 326),
    (23, 147),
    (23, 327),
    (24, 163),
    (25, 24),
    (25, 155),
    (26, 28),
    (28, 142),
    (30, 31),
    (31, 32),
    (32, 33),
    (33, 361),
    (34, 99),
    (34, 132),
    (35, 36),
    (36, 101),
    (37, 296),
    (38, 39),
    (38, 229),
    (39, 40),
    (40, 41),
    (41, 42),
    (42, 136),
    (42, 246),
    (43, 44),
    (44, 177),
    (45, 46),
    (46, 47),
    (47, 48),
    (48, 49),
    (49, 50),
    (50, 51),
    (51, 52),
    (52, 53),
    (53, 74),
    (54, 111),
    (54, 436),
    (57, 58),
    (58, 59),
    (58, 112),
    (59, 60),
    (59, 113),
    (60, 81),
    (60, 437),
    (61, 62),
    (61, 69),
    (62, 63),
    (63, 64),
    (64, 65),
    (65, 196),
    (66, 90),
    (67, 15),
    (68, 69),
    (68, 455),
    (69, 70),
    (70, 71),
    (71, 72),
    (72, 73),
    (73, 106),
    (75, 83),
    (75, 412),
    (76, 152),
    (77, 166),
    (77, 299),
    (78, 54),
    (81, 82),
    (82, 130),
    (83, 4),
    (84, 75),
    (85, 86),
    (85, 96),
    (86, 126),
    (87, 88),
    (87, 409),
    (88, 117),
    (88, 403),
    (89, 369),
    (90, 91),
    (91, 93),
    (92, 98),
    (93, 92),
    (94, 93),
    (95, 91),
    (95, 94),
    (96, 97),
    (97, 30),
    (97, 98),
    (98, 185),
    (99, 100),
    (99, 308),
    (100, 35),
    (100, 248),
    (101, 103),
    (101, 265),
    (101, 266),
    (102, 24),
    (103, 25),
    (103, 283),
    (103, 285),
    (104, 143),
    (105, 34),
    (105, 339),
    (106, 66),
    (111, 57),
    (111, 449),
    (112, 113),
    (113, 443),
    (114, 115),
    (114, 444),
    (115, 116),
    (115, 118),
    (116, 88),
    (116, 125),
    (117, 85),
    (117, 407),
    (118, 125),
    (125, 445),
    (126, 89),
    (129, 130),
    (129, 440),
    (130, 87),
    (131, 67),
    (131, 374),
    (132, 307),
    (133, 39),
    (133, 134),
    (134, 40),
    (134, 135),
    (135, 41),
    (135, 305),
    (136, 137),
    (137, 43),
    (137, 138),
    (138, 44),
    (138, 139),
    (139, 140),
    (140, 304),
    (141, 182),
    (141, 318),
    (142, 293),
    (143, 144),
    (144, 145),
    (145, 146),
    (146, 48),
    (147, 151),
    (151, 153),
    (151, 332),
    (152, 102),
    (153, 76),
    (155, 26),
    (155, 37),
    (156, 104),
    (157, 156),
    (159, 157),
    (161, 159),
    (161, 297),
    (162, 77),
    (162, 161),
    (163, 162),
    (163, 277),
    (165, 167),
    (166, 165),
    (167, 180),
    (170, 18),
    (171, 17),
    (171, 184),
    (172, 96),
    (172, 411),
    (173, 94),
    (173, 172),
    (175, 131),
    (177, 178),
    (178, 179),
    (179, 180),
    (180, 183),
    (182, 179),
    (182, 323),
    (183, 45),
    (184, 11),
    (184, 470),
    (185, 7),
    (185, 186),
    (186, 473),
    (187, 1),
    (187, 5),
    (187, 434),
    (188, 2),
    (189, 190),
    (190, 191),
    (191, 192),
    (192, 193),
    (193, 194),
    (194, 195),
    (195, 129),
    (196, 197),
    (197, 66),
    (198, 199),
    (199, 200),
    (200, 201),
    (201, 13),
    (202, 203),
    (203, 204),
    (204, 205),
    (205, 206),
    (206, 207),
    (207, 208),
    (208, 209),
    (209, 210),
    (210, 211),
    (211, 212),
    (212, 213),
    (213, 214),
    (214, 215),
    (215, 216),
    (216, 217),
    (217, 218),
    (218, 219),
    (219, 220),
    (220, 221),
    (221, 222),
    (222, 223),
    (223, 224),
    (224, 225),
    (225, 226),
    (226, 227),
    (227, 228),
    (228, 53),
    (229, 230),
    (230, 231),
    (231, 232),
    (232, 233),
    (233, 234),
    (234, 235),
    (235, 236),
    (236, 237),
    (237, 238),
    (238, 239),
    (239, 240),
    (240, 241),
    (241, 242),
    (242, 243),
    (243, 244),
    (244, 245),
    (245, 49),
    (246, 247),
    (247, 43),
    (248, 249),
    (249, 250),
    (250, 251),
    (251, 252),
    (252, 253),
    (253, 254),
    (254, 255),
    (255, 256),
    (256, 257),
    (257, 258),
    (258, 259),
    (259, 260),
    (260, 261),
    (261, 262),
    (262, 263),
    (263, 264),
    (264, 48),
    (265, 102),
    (266, 267),
    (267, 268),
    (268, 269),
    (269, 270),
    (270, 271),
    (271, 272),
    (272, 273),
    (273, 274),
    (274, 275),
    (275, 276),
    (276, 144),
    (277, 278),
    (278, 279),
    (279, 280),
    (280, 281),
    (281, 282),
    (282, 143),
    (283, 284),
    (284, 37),
    (285, 286),
    (286, 287),
    (287, 288),
    (288, 289),
    (289, 290),
    (290, 291),
    (291, 292),
    (292, 104),
    (293, 294),
    (294, 295),
    (295, 104),
    (296, 142),
    (297, 298),
    (298, 156),
    (299, 300),
    (300, 301),
    (301, 302),
    (302, 303),
    (303, 45),
    (304, 167),
    (305, 306),
    (306, 136),
    (307, 133),
    (308, 309),
    (309, 310),
    (310, 311),
    (311, 312),
    (312, 313),
    (313, 314),
    (314, 315),
    (315, 316),
    (316, 317),
    (317, 141),
    (318, 319),
    (319, 320),
    (320, 321),
    (321, 322),
    (322, 46),
    (323, 324),
    (324, 183),
    (325, 99),
    (326, 100),
    (327, 328),
    (328, 329),
    (329, 330),
    (330, 331),
    (331, 102),
    (332, 333),
    (333, 152),
    (334, 335),
    (335, 336),
    (336, 337),
    (337, 38),
    (338, 105),
    (339, 340),
    (340, 341),
    (341, 342),
    (342, 343),
    (343, 344),
    (344, 345),
    (345, 346),
    (346, 347),
    (347, 348),
    (348, 349),
    (349, 350),
    (350, 351),
    (351, 352),
    (352, 353),
    (353, 354),
    (354, 355),
    (355, 356),
    (356, 357),
    (357, 358),
    (358, 359),
    (359, 360),
    (360, 50),
    (361, 362),
    (362, 363),
    (363, 364),
    (364, 365),
    (365, 366),
    (366, 367),
    (367, 368),
    (368, 105),
    (369, 370),
    (370, 371),
    (371, 372),
    (372, 373),
    (373, 175),
    (374, 375),
    (375, 376),
    (376, 377),
    (377, 378),
    (378, 379),
    (379, 380),
    (380, 381),
    (381, 382),
    (382, 383),
    (383, 384),
    (384, 385),
    (385, 386),
    (386, 387),
    (387, 388),
    (388, 389),
    (389, 390),
    (390, 391),
    (391, 392),
    (392, 393),
    (393, 394),
    (394, 395),
    (395, 396),
    (396, 397),
    (397, 398),
    (398, 399),
    (399, 400),
    (400, 401),
    (401, 402),
    (402, 52),
    (403, 404),
    (404, 405),
    (405, 406),
    (406, 89),
    (407, 408),
    (408, 126),
    (409, 410),
    (410, 172),
    (411, 92),
    (412, 413),
    (413, 414),
    (414, 415),
    (415, 416),
    (416, 417),
    (417, 418),
    (418, 419),
    (419, 420),
    (420, 421),
    (421, 95),
    (422, 423),
    (423, 424),
    (424, 425),
    (425, 426),
    (426, 427),
    (427, 428),
    (428, 429),
    (429, 430),
    (430, 431),
    (431, 432),
    (432, 433),
    (433, 90),
    (434, 435),
    (435, 78),
    (436, 57),
    (437, 438),
    (438, 439),
    (439, 87),
    (440, 441),
    (441, 442),
    (442, 173),
    (443, 114),
    (444, 118),
    (445, 446),
    (446, 447),
    (447, 448),
    (448, 89),
    (449, 450),
    (450, 112),
    (451, 452),
    (452, 453),
    (453, 454),
    (454, 18),
    (455, 456),
    (456, 457),
    (457, 458),
    (458, 459),
    (459, 460),
    (460, 461),
    (461, 462),
    (462, 463),
    (463, 464),
    (464, 465),
    (465, 466),
    (466, 467),
    (467, 468),
    (468, 469),
    (469, 17),
    (470, 471),
    (471, 8),
    (472, 170),
    (473, 474),
    (474, 475),
    (475, 9),
]
ordering = [
    [187],
    [1, 5, 434],
    [6, 188, 435],
    [2, 84, 78, 422],
    [3, 75, 54, 189, 423],
    [83, 111, 190, 412, 424, 436],
    [4, 57, 191, 413, 425, 449],
    [61, 58, 68, 192, 414, 426, 450],
    [62, 59, 112, 69, 193, 415, 427, 455],
    [63, 60, 113, 70, 194, 416, 428, 456],
    [64, 81, 71, 195, 417, 429, 437, 443, 457],
    [65, 82, 129, 114, 72, 418, 430, 438, 458],
    [130, 115, 73, 196, 419, 431, 439, 440, 444, 459],
    [87, 116, 118, 106, 197, 420, 432, 441, 460],
    [66, 88, 125, 409, 421, 433, 442, 461],
    [90, 117, 173, 95, 403, 410, 445, 462],
    [91, 85, 172, 94, 404, 407, 446, 463],
    [93, 96, 86, 405, 408, 411, 447, 464],
    [92, 97, 126, 406, 448, 465],
    [98, 30, 89, 466],
    [185, 31, 369, 467],
    [7, 32, 186, 370, 468],
    [33, 171, 198, 371, 469, 473],
    [17, 184, 199, 361, 372, 474],
    [11, 200, 362, 373, 451, 470, 475],
    [175, 9, 12, 201, 363, 452, 471],
    [13, 131, 8, 364, 453, 472],
    [14, 67, 170, 365, 374, 454],
    [15, 18, 366, 375],
    [16, 19, 367, 376],
    [20, 202, 338, 368, 377],
    [21, 105, 203, 334, 378],
    [34, 22, 204, 325, 335, 339, 379],
    [132, 99, 23, 205, 326, 336, 340, 380],
    [100, 147, 206, 307, 308, 327, 337, 341, 381],
    [38, 35, 133, 151, 207, 248, 309, 328, 342, 382],
    [39, 36, 134, 153, 208, 229, 249, 310, 329, 332, 343, 383],
    [40, 101, 135, 76, 209, 230, 250, 311, 330, 333, 344, 384],
    [41, 103, 152, 210, 231, 251, 265, 266, 305, 312, 331, 345, 385],
    [42, 102, 25, 211, 232, 252, 267, 283, 285, 306, 313, 346, 386],
    [24, 155, 136, 212, 233, 246, 253, 268, 284, 286, 314, 347, 387],
    [163, 26, 37, 137, 213, 234, 247, 254, 269, 287, 315, 348, 388],
    [43, 28, 162, 138, 214, 235, 255, 270, 277, 288, 296, 316, 349, 389],
    [44, 142, 161, 77, 139, 215, 236, 256, 271, 278, 289, 317, 350, 390],
    [177, 159, 166, 140, 141, 216, 237, 257, 272, 279, 290, 293, 297, 299, 351, 391],
    [
        178,
        157,
        165,
        182,
        217,
        238,
        258,
        273,
        280,
        291,
        294,
        298,
        300,
        304,
        318,
        352,
        392,
    ],
    [179, 156, 167, 218, 239, 259, 274, 281, 292, 295, 301, 319, 323, 353, 393],
    [180, 104, 219, 240, 260, 275, 282, 302, 320, 324, 354, 394],
    [183, 143, 220, 241, 261, 276, 303, 321, 355, 395],
    [45, 144, 221, 242, 262, 322, 356, 396],
    [46, 145, 222, 243, 263, 357, 397],
    [47, 146, 223, 244, 264, 358, 398],
    [48, 224, 245, 359, 399],
    [49, 225, 360, 400],
    [50, 226, 401],
    [51, 227, 402],
    [52, 228],
    [53],
    [74],
]
graph = create_graph(num_vertices, edges)


mark_node(graph, ordering)
chaotic_map_function = logistic_tent_map
num_populations = 20
mark_node(graph, ordering)
populations = earn_populations(num_populations, ordering)
reverse_individual_populations = earn_reverse_population(populations)
new_populations = gather_populations(populations, reverse_individual_populations)
sorte_population = sorted_population(graph, new_populations)

# for i, ordering in enumerate(sorte_population):
#         crossing = count_crossings(graph,ordering)
#         print(f"{ordering}, Crossing: {crossing}")

T = 50
w_start_population = 0.9
w_end_population = 0.1
for time in range(T):
    weight_factor_population = (
        w_start_population - (w_start_population - w_end_population) * (time / T) ** 2
    )

    # print('jjjjjjjjjjjjjjjjjjjjjjjjjj',sorte_population)
    # for i, ordering in enumerate(sorte_population):
    #     crossing = count_crossings(graph,ordering)
    #     print(f"{ordering}, Crossing: {crossing}")
    finder_bird_num = round(weight_factor_population * num_populations * 2)
    finder_population = finder_bird(finder_bird_num, sorte_population, time, T)

    # print('ffffffffffffffffffffffff',sorte_population)
    sorte_population = sorted_population(graph, sorte_population)

    # print('--------------------------------------------')
    # for i, ordering in enumerate(sorte_population):
    #     crossing = count_crossings(graph,ordering)
    #     print(f"{ordering}, Crossing: {crossing}")

    p_best_bird = sorte_population[0]
    worst_bird = sorte_population[-1]
    # print('p_best_bird',p_best_bird)
    # print('worst_bird',worst_bird)
    follow_bird_num = num_populations * 2 - finder_bird_num

    # 传入搜索者的末尾数量
    all_num_bird = num_populations * 2
    follow_bird(
        finder_bird_num, sorte_population, p_best_bird, worst_bird, all_num_bird
    )

    # 警戒者
    random_integers = random.sample(range(len(sorte_population)), 20)  # 有多少

    j = 0
    for label_xu in random_integers:
        update_node_positions(graph, sorte_population[label_xu])
        # aaaaa= copy.deepcopy(sorte_population[label_xu])
        if j % 2 == 0:
            sorte_population[label_xu] = reverse_gravity_heuristic(
                sorte_population[label_xu], graph
            )
        else:

            sorte_population[label_xu] = gravity_heuristics(
                sorte_population[label_xu], graph
            )
        j += 1
    sorte_population = sorted_population(graph, sorte_population)


for i, ordering in enumerate(sorte_population[:5]):
    crossing = count_crossings(graph, ordering)
    print(f"{ordering}, Crossing: {crossing}")


# for i, ordering in enumerate(sorte_population):

#     crossing = count_crossings(graph,ordering)
#     print(f"{ordering}, Crossing: {crossing}")
